class Solution {
public:
    int dir[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
                                        
    double knightProbability(int n, int k, int row, int column) {
        vector<vector<vector<double>>> dp(k+1,vector<vector<double>>(n+1,vector<double>(n+1,0)));
        
        dp[0][row][column] = 1;
        
        double ret = 0;
        
        for(int step = 0;step < k;step++){
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    if(dp[step][i][j] == 0) continue;
                    
                    for(int p = 0;p < 8;p++){
                        int x = i + dir[p][0];
                        int y = j + dir[p][1];
                         if(x >= 0 && x < n && y >= 0 && y < n){
                             dp[step+1][x][y] += dp[step][i][j] / 8;
                             
                        }
                    }
                }
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(dp[k][i][j] != 0){
                    ret += dp[k][i][j];
                } 
            }
        }
        return ret;
    }
};
